ZK-SNARKs 離散対数問題

英語で、Discrete Logarithm Problem。

モジュラ演算：Mod

a mod b = c

を考える。

aをbで割ったときのあまりをcを表現する

12 mod 2 = 0

7 mod 3 = 1

あまりは0〜b-1になる。

原始根

3以上の素数pと1以上p-1以下の整数rが以下の性質を満たす時、rをmod pの原始根という。

たとえば、p=13の場合、原始根は2,6,7,11であることが知られている。

6の場合

6 mod 13 = 6

6^2 mod 13 = 36 mod 13 = 10

6^3 mod 13 = 216 mod 13 = 8

6^4 mod 13 = 1296 mod 13 = 9

6^5 mod 13 = 7776 mod 13 = 2

6^6 mod 13 = 46656 mod 13 = 12

6^7 mod 13 = 279936 mod 13 = 7

6^8 mod 13 = 1679616 mod 13 = 3

6^9 mod 13 = 10077696 mod 13 = 5

6^10 mod 13 = 60466176 mod 13 = 4

6^11 mod 13 = 362797056 mod 13 = 11

原始根を使うと2〜p-1の間で右辺の計算結果が重複がないという性質がある。

つまり

p: 素数

g: 原始根

A: {2, 3, 4, ,,,,,,,p-1} = 右辺の値

r: {1,2,3,,,,,,,p-2} = べき乗数

$ g^r mod \quad p = A

とする時、rとAが一対一対応する。

Aの値を与えられた時に、対応するrを求めるにはべき乗計算とモジュラ計算を次数の少ない方から順番に計算するしか求める方法がない。これが離散対数問題。

rのことを底gについてのAの離散対数という。